package com.bobo.px.impl;

import com.bobo.px.PxImpl;
import com.bobo.util.Utils;

public class Heap implements PxImpl {
    @Override
    public void px(int[] data) {
        //
        for (int i = data.length/2-1; i >=0 ; i--) {
            int k=i;
            int temp=data[i];
            int index=2*k+1;//左
            while(index<data.length){
                if(index+1<data.length){
                    if(data[index+1]>data[index]){
                        index=index+1;
                    }
                }
                if (data[index]>temp){
                    data[k]=data[index];
                    k=index;
                    index=2*k+1;
                }else {
                    break;
                }
            }
            data[k]=temp;
        }

        int ln=data.length;
        for (int i = ln-1; i >=0 ; i--) {
            int max=data[0];
            data[0]=data[i];
            data[i]=max;
            int k=0;
            int temp=data[k];
            int index=2*k+1;//左
            while(index<i){
                if(index+1<i){
                    if(data[index+1]>data[index]){
                        index=index+1;
                    }
                }
                if (data[index]>temp){
                    data[k]=data[index];
                    k=index;
                    index=2*k+1;
                }else {
                    break;
                }
            }
            data[k]=temp;
        }


    }
}
